package solution4;

public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int k = (len1 + len2) / 2 + 1;
        if ((len1 + len2) % 2 == 1) {
            return findkth(nums1, nums2, k);
        }
        else {
            return (findkth(nums1, nums2, k-1) + findkth(nums1, nums2, k)) / 2.0;
        }

    }

    private static double findkth(int[] nums1, int[] nums2, int k) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        if (k <= 0 || k > len1 + len2) throw new IllegalArgumentException("k: 0 < k <= len1 + len2");

        if (len1 > len2) {
            return findkth(nums2, nums1, k);
        }

        if (len1 == 0) {
            return nums2[k - 1];
        }

        if (k == 1) {
            return nums1[0] < nums2[0] ? nums1[0] : nums2[0];
        }
        //首先假设数组nums1和nums2的元素个数都大于k/2，比较nums1[k/2-1]和nums2[k/2-1]两个元素
        int pos1 = k / 2 < len1 ? k / 2 : len1;
        int pos2 = k - pos1;
        //如果相等，则找到第k小元素，即为相等的这个元素
        if (nums1[pos1 - 1] == nums2[pos2 -1]) {
            return nums1[pos1 - 1];
        }
        //如果一个nums1[pos1 - 1]小，那么它前面的元素都一定在合并数组中的前k小元素中，然后只递归比较其后面的数组和nums2数组的前k-pos1小
        else if (nums1[pos1 - 1] < nums2[pos2 - 1]) {
            int[] temp = new int[len1 - pos1];
            System.arraycopy(nums1, pos1, temp, 0, temp.length);
            return findkth(temp, nums2, k - pos1);
        }
        //如果一个nums2[pos2 - 1]小，那么它前面的元素都一定在合并数组中的前k小元素中，然后只递归比较其后面的数组和nums1数组的前k-pos2小
        else {
            int[] temp = new int[len2 - pos2];
            System.arraycopy(nums2, pos2, temp, 0, temp.length);
            return findkth(nums1, temp, k - pos2);
        }
    }
}